// 实现加减乘除和括号四则运算
// 思路：
//   1. 把输入的字符串表达式如：9+(3-1)*3+10/2转换为term结构体数组，结构体描述是符号还是数字。
//   2. 利用栈把中缀表达式term数组转换为后缀表达式term数组
//   3. 利用栈运算得出结果
#include <stdio.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100

typedef int priority;

typedef int status;

enum term_type
{
    PLUS = 0,      // +
    MINUS = 1,     // -
    MULTIPLY = 2,  // *
    DIVIDED = 3,   // /
    L_BRACKET = 4, // (
    R_BRACKET = 5, // )
    DATA = 6,      // 数字
    END = -1       // 结束符
};

char op_char[] = {'+', '-', '*', '/'}; //打印计算过程使用

/*描述参与运算的数字和符号的结构体*/
typedef struct term
{
    int data;
    enum term_type op;
} term;

/*数组实现的栈结构体*/
typedef struct
{
    term data[MAXSIZE];
    int top;
} array_stack;

/*初始化栈*/
status array_stack_init(array_stack *stack)
{
    stack->top = -1;
    return OK;
}

/*入栈*/
status array_stack_push(array_stack *stack, term e)
{
    if (stack->top == MAXSIZE - 1)
        return ERROR;
    stack->data[stack->top + 1] = e;
    stack->top++;
    return OK;
}

/*出栈*/
status array_stack_pop(array_stack *stack, term *e)
{
    if (stack->top == -1)
        return ERROR;
    *e = stack->data[stack->top];
    stack->top--;
    return OK;
}

/*运算表达式转换成term结构体数组*/
status expression_to_array(term *term_p, char *p)
{
    // unsigned char *p;
    // p = jisuan;
    int number = 0;

    int i = -1;

    while (*p != '\0' && *p != '\n')
    {
        if (*p <= '9' && *p >= '0')
        {
            if (number == 0)
                i++;
            number = number * 10 + (int)((*p) - '0');
        }
        else
        {
            if (number != 0)
            {
                term_p[i].data = number;
                term_p[i].op = DATA;
                number = 0;
            }
            i++;
            term_p[i].data = 0;
            switch (*p)
            {
            case '+':
                term_p[i].op = PLUS;
                break;
            case '-':
                term_p[i].op = MINUS;
                break;
            case '*':
                term_p[i].op = MULTIPLY;
                break;
            case '/':
                term_p[i].op = DIVIDED;
                break;
            case '(':
                term_p[i].op = L_BRACKET;
                break;
            case ')':
                term_p[i].op = R_BRACKET;
                break;
            }
        }
        p++;
    }
    if (number != 0)
    {
        term_p[i].op = DATA;
        term_p[i].data = number;
        term_p[++i].op = END;
        term_p[++i].data = 0;
    }
    else
    {
        term_p[i].op = END;
        term_p[i].data = 0;
    }
    return OK;
}

/* 
* 运算符优先级判断0是t1=t2，1是t1>t2 -1是t1<t2
*
*    +   -   *   /
* +  0,  0, -1, -1
* -  0,  0, -1, -1
* *  1,  1,  0,  0
* /  1,  1,  0,  0
*/
priority priority_calc(term t1, term t2)
{
    priority priorityTable[4][4] =
        {{0, 0, -1, -1},
         {0, 0, -1, -1},
         {1, 1, 0, 0},
         {1, 1, 0, 0}};

    return priorityTable[t1.op][t2.op];
}

/*转换为后缀表达式term数组*/
status to_bolan(term *term_p, term *term_out)
{
    array_stack stack;
    array_stack_init(&stack);
    int i = 0;
    while (term_p->op != END)
    {
        if (term_p->op == DATA)
        {
            term_out[i] = *term_p;
            i++;
        }
        else
        {
            if (stack.top == -1 || term_p->op == L_BRACKET || stack.data[stack.top].op == L_BRACKET)
            {
                array_stack_push(&stack, *term_p);
            }
            else if (term_p->op == R_BRACKET)
            {
                term e;
                array_stack_pop(&stack, &e);
                while (e.op != L_BRACKET && stack.top != -1)
                {
                    term_out[i] = e;
                    i++;
                    array_stack_pop(&stack, &e);
                }
            }
            else if (priority_calc(*term_p, stack.data[stack.top]) == -1)
            {

                while (stack.top != -1 && stack.data[stack.top].op != L_BRACKET)
                {
                    term e;
                    array_stack_pop(&stack, &e);
                    term_out[i] = e;
                    i++;
                }
                array_stack_push(&stack, *term_p);
            }
            else
            {
                array_stack_push(&stack, *term_p);
            }
        }
        term_p++;
    }
    while (stack.top != -1)
    {
        term e;
        array_stack_pop(&stack, &e);
        term_out[i] = e;
        i++;
    }
    term term_end;
    term_end.op = END;
    term_end.data = 0;
    term_out[i] = term_end;
    return OK;
}

/*运算t1 t2*/
status calc_term(term t1, term t2, term term_op, int *result)
{

    switch (term_op.op)
    {
    case PLUS:
        *result = t1.data + t2.data;
        break;
    case MINUS:
        *result = t1.data - t2.data;
        break;
    case MULTIPLY:
        *result = t1.data * t2.data;
        break;
    case DIVIDED:
        *result = (int)(t1.data / t2.data);
        break;
    default:
        return ERROR;
        break;
    }
    return OK;
}

/*运算整个表达式*/
status calc(term *term_p, int *result)
{
    array_stack stack;
    array_stack_init(&stack);
    while (term_p->op != END)
    {
        if (term_p->op == DATA)
        {
            array_stack_push(&stack, *term_p);
        }
        else
        {
            term e1;
            array_stack_pop(&stack, &e1);

            term e2;
            array_stack_pop(&stack, &e2);

            term term_result;
            term_result.op = DATA;

            calc_term(e2, e1, *term_p, &(term_result.data));

            printf("%d%c%d=%d\n", e2.data, op_char[term_p->op], e1.data, term_result);

            array_stack_push(&stack, term_result);
        }
        term_p++;
    }
    term result_end;
    array_stack_pop(&stack, &result_end);
    *result = result_end.data;
    return OK;
}

/*返回s字符串c字符指针*/
char *strchr(const char *s, int c)
{
    for (; *s != (char)c; ++s)
        if (*s == '\0')
            return NULL;
    return (char *)s;
}

int main(int argc, char const *argv[])
{
    char jisuan[MAXSIZE], *p; // 9+(3-1)*3+10/2

    fgets(jisuan, MAXSIZE, stdin);

    if ((p = strchr(jisuan, '\n')) != NULL)
        *p = '\0'; //最后一个字符是\n手动将\n位置处的值变为0

    term term_s[MAXSIZE];

    expression_to_array(term_s, jisuan);

    term term_out_s[MAXSIZE];

    to_bolan(term_s, term_out_s);

    // int i;
    // for (i = 0; i < MAXSIZE; i++)
    // {
    //     printf("[%d]OP=%d  DATA=%d \n", i, term_out_s[i].op, term_out_s[i].data);
    // }

    int result;
    calc(term_out_s, &result);

    printf("%s=%d", jisuan, result);
    return 0;
}
